package com.huangyi;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //验证栈序列
        class Solution {
            public boolean validateStackSequences(int[] pushed, int[] popped) {
                // 可用 Deque<Integer> stack = new ArrayDeque<>(); 更高效
                java.util.Stack<Integer> stack = new java.util.Stack<>();

                int i = 0, j = 0, n = pushed.length;
                while (i < n) {
                    stack.push(pushed[i++]);                 // 先按 pushed 顺序入栈
                    // 只要栈顶等于 popped[j]，就连续弹出并推进 j
                    while (!stack.isEmpty() && stack.peek() == popped[j]) {
                        stack.pop();
                        j++;
                    }
                }
                // 若能完全匹配，栈应被清空（等价于 j == n）
                return stack.isEmpty();
            }
        }

        //N叉树的层序遍历
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}
        public Node(int _val) { val = _val; }
        public Node(int _val, List<Node> _children) {
        val = _val; children = _children;
        }
    };
        class Solution2 {

            public List<List<Integer>> levelOrder(Node root) {
                List<List<Integer>> result = new ArrayList<>();
                if (root == null) return result;  // 空树

                Queue<Node> q = new ArrayDeque<>();
                q.offer(root);

                while (!q.isEmpty()) {
                    int sz = q.size();                   // 锁定本层大小
                    List<Integer> level = new ArrayList<>(sz);

                    for (int i = 0; i < sz; i++) {
                        Node node = q.poll();            // 出队当前层结点
                        level.add(node.val);

                        if (node.children != null) {     // 判空再遍历子结点
                            for (Node ch : node.children) {
                                if (ch != null) q.offer(ch);
                            }
                        }
                    }
                    result.add(level);                   // 收录本层
                }
                return result;
            }
        }


    }
}